import numpy as np
import time


# 随机创建矩阵,还得处理无解情形,要使生成的数独必然有解（唯一解/多解）
class CreateNew(object):

    def __init__(self, size):
        self.mat = np.zeros([9, 9], dtype=int)
        self.count = 0
        self.size = size
        self.creat()

    def creat(self):
        while self.count < self.size:  # 初始化生成num个数字
            num = np.random.randint(1, 10)  # 随机的数字
            x = np.random.randint(0, 9)  # 随机的x坐标
            y = np.random.randint(0, 9)  # 随机的y坐标
            if (num not in self.mat[x, :]) and (num not in self.mat[:, y]):   # 先确保横竖不重复
                # 判断(x,y)所在的分块是否已包含数字num
                if (x in [3*(x//3), 3*(x//3)+1, 3*(x//3)+2]) and (y in [3*(y//3), 3*(y//3)+1, 3*(y//3)+2]) and \
                        (num not in self.mat[3*(x//3):3*(x//3)+3, 3*(y//3):3*(y//3)+3]) and (self.mat[x, y] == 0):
                    self.mat[x, y] = num
                    self.count += 1


# 传入矩阵--->输出空值的位置及对应的所有可能取值
# (point_x-->int, point_y-->int, possible_value-->set)
def solve_sudo(mat):
    """按可能数量升序返回空值坐标和可能值"""
    s = set(range(1, 10))
    ls = []
    zero_index = np.where(mat == 0)
    for x, y in zip(zero_index[0], zero_index[1]):
        s1 = set(mat[x, :])
        s2 = set(mat[:, y])
        s3 = set(mat[3*(x//3):3*(x//3)+3, 3*(y//3):3*(y//3)+3].ravel())
        possible = s - (s1 | s2 | s3)
        ls.append((x, y, possible))     # 获得空白位的可能填数,可能填数可以空集，在loop_back()判断

    point = sorted(ls, key=lambda x: len(x[-1]))[0]     # 只取可能性最少的点，降低无效迭代次数
    return point    # -->元组


def loop_back(point):
    while len(point[2]) > 0:  # 列表第一个点循环取可能值
        mat[point[0], point[1]] = point[2].pop()
        new_point = solve_sudo(mat)  # 计算出传入mat的空值点可能取值列表
        try:    # 出现一个异常当解出数独后还继续迭代，抛出即可，但拖延了一点时间，这是待改进的地方
            if new_point[2] != set():
                loop_back(new_point)  # 迭代
        except:
            pass
        if sum(mat.ravel()) == 45*9:    # 显然所有数字填满时总和是确定的
            return mat
        else:
            # 若结束嵌套说明发生回溯，则将坐标归0，以上当作没发生过
            mat[point[0], point[1]] = 0


if __name__ == '__main__':
    t = time.time()
    # c = CreateNew(10)
    # mat = c.mat
    # 据说是最难数独-->求解约0.6~0.9s
    # mat = np.array([
    #     [8, 0, 0,   0, 0, 0,   0, 0, 0],
    #     [0, 0, 3,   6, 0, 0,   0, 0, 0],
    #     [0, 7, 0,   0, 9, 0,   2, 0, 0],
    #
    #     [0, 5, 0,   0, 0, 7,   0, 0, 0],
    #     [0, 0, 0,   0, 4, 5,   7, 0, 0],
    #     [0, 0, 0,   1, 0, 0,   0, 3, 0],
    #
    #     [0, 0, 1,   0, 0, 0,   0, 6, 8],
    #     [0, 0, 8,   5, 0, 0,   0, 1, 0],
    #     [0, 9, 0,   0, 0, 0,   4, 0, 0]])
    # 以下是随便找的数独-->求解约0.02~0.2s
    # mat = np.array([[2, 3, 9, 0, 4, 0, 0, 0, 0],
    #                 [7, 0, 0, 0, 0, 0, 6, 9, 0],
    #                 [0, 0, 1, 0, 5, 9, 0, 4, 0],
    #                 [4, 0, 7, 8, 9, 0, 5, 6, 0],
    #                 [0, 6, 8, 1, 3, 5, 0, 7, 0],
    #                 [5, 0, 3, 0, 0, 0, 0, 1, 0],
    #                 [8, 0, 0, 0, 0, 4, 7, 0, 0],
    #                 [0, 7, 4, 0, 8, 0, 1, 0, 5],
    #                 [1, 0, 0, 2, 7, 0, 0, 0, 9]])
    mat = np.array([[0, 6, 1, 0, 3, 0, 0, 2, 0],
                    [0, 5, 0, 0, 0, 8, 1, 0, 7],
                    [0, 0, 0, 0, 0, 7, 0, 3, 4],
                    [0, 0, 9, 0, 0, 6, 0, 7, 8],
                    [0, 0, 3, 2, 0, 9, 5, 0, 0],
                    [5, 7, 0, 3, 0, 0, 9, 0, 0],
                    [1, 9, 0, 7, 0, 0, 0, 0, 0],
                    [8, 0, 2, 4, 0, 0, 0, 6, 0],
                    [0, 4, 0, 0, 1, 0, 2, 5, 0]])
    print('待解数独')
    print(mat)
    point = solve_sudo(mat)
    arr = loop_back(point)
    print('计算中...')
    print('解---------------')
    print(arr)
    print(f'耗时{time.time()-t}s')
